package listbyorder.access001_100.test93;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/6 8:49
 */
public class Solution1 {

    // 复制IP地址
    // 方法一：经典的回溯算法
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        dfs(s, 0, new StringBuilder(), 0, ans);
        return ans;
    }

    private void dfs(String s, int start, StringBuilder path, int count, List<String> ans) {
        if ((s.length() - start) > 3 * (4 - count)) {
            return;  // 这种肯定无法生成有效的结果
        }
        if (start == s.length()) {
            if (count == 4) {
                ans.add(new String(path.substring(0, path.length() - 1)));
            }
            return;
        }
        if (start > s.length() || count == 4) {
            // 如果start超出范围或者count提前等于4，直接结束
            return;
        }

        // 保存之前的数，用作递归
        StringBuilder before = new StringBuilder(path);

        // 首先是添加一位的操作
        path.append(s.charAt(start) + "" + ".");
        dfs(s, start + 1, path, count + 1, ans);

        // 如果当前位置是0，直接返回, 0可以单独用作一位
        if (s.charAt(start) == '0') return;

        // 然后是添加两位的操作
        if (start + 1 < s.length()) {
            path = new StringBuilder(before);
            path.append(s.substring(start, start + 2) + ".");
            dfs(s, start + 2, path, count + 1, ans);
        }

        // 然后就是添加三位的操作
        if (start + 2 < s.length()) {
            int num = Integer.parseInt(s.substring(start, start + 3));
            if (num <= 255 && num > 0) {
                path = new StringBuilder(before);
                path.append(s.substring(start, start + 3) + ".");
                dfs(s, start + 3, path, count + 1, ans);
            }
        }
    }
}
